package com.chapter2.sort;

/** 
 * @ClassName: MergeSortDown2Up 
 * @Description: 归并排序（自底而上） 
 * @author minjun minjun@bw30.com
 * @date 2015-2-15 上午9:43:50 
 *  
 */
public class MergeSortDown2Up extends AbstractSort{
	
	private int[] aux;

	@Override
	public void sort(int[] a) {
		int len=a.length;
		aux=new int[len];
		//为了保证所有数据
		for(int size=1;size<len;size=size<<1){
			//从左到右，选择要被合并的数组
			for(int start=0;start<len-size;start+=size<<1){
				//合并，当长度超过最大索引时，采用最大索引
				merge(a,start,start+size-1,Math.min(start+(size<<1)-1, len-1));
			}
		}
		
	}

	/** 
	* @Title: merge 
	* @Description: 归并 
	* @param @param a
	* @param @param start
	* @param @param i
	* @param @param min    设定文件 
	* @return void    返回类型 
	* @throws 
	*/ 
	private void merge(int[] a, int start, int mid, int end) {
		for(int k=start;k<=end;k++) aux[k]=a[k];
		int i=start;
		int j=mid+1;
		for(int k=start;k<=end;k++){
			if(i>mid) 						a[k]=aux[j++];
			else if(j>end) 					a[k]=aux[i++];
			else if(less(aux[j], aux[i])) 	a[k]=aux[j++];
			else 							a[k]=aux[i++];
		}
	}

}
